package com.ln.leetcode._1240;

import org.junit.Test;

/**
 * 1240. 铺瓷砖
 * 你是一位施工队的工长，根据设计师的要求准备为一套设计风格独特的房子进行室内装修。
 * 房子的客厅大小为 n x m，为保持极简的风格，需要使用尽可能少的 正方形 瓷砖来铺盖地面。
 * 假设正方形瓷砖的规格不限，边长都是整数。
 * 请你帮设计师计算一下，最少需要用到多少块方形瓷砖？
 * <p>
 * 示例 1：
 * 输入：n = 2, m = 3
 * 输出：3
 * 解释：3 块地砖就可以铺满卧室。
 * 2 块 1x1 地砖
 * 1 块 2x2 地砖
 * <p>
 * 示例 2：
 * 输入：n = 5, m = 8
 * 输出：5
 * <p>
 * 示例 3：
 * 输入：n = 11, m = 13
 * 输出：6
 */
public class Solution {

    @Test
    public void test() {
        System.out.println(tilingRectangle(2, 3));
    }

    int ans = 0;

    /**
     * @param n 长 - 行数
     * @param m 宽 - 列数
     * @return
     */
    public int tilingRectangle(int n, int m) {
        ans = Math.max(n, m);
        boolean[][] rect = new boolean[n][m];
        dfs(0, 0, rect, 0);
        return ans;
    }

    /**
     * @param x     行下标
     * @param y     列下标
     * @param rect  矩形二维数组，内部有boolean组成，如果为true，标识已被填充
     * @param count 计数
     */
    public void dfs(int x, int y, boolean[][] rect, int count) {
        int n = rect.length;
        int m = rect[0].length;

        // 退出的条件
        // 当 count >= ans，表示已经不存在最优解，直接返回
        if (count >= ans) {
            return;
        }

        // 当行下标 >= 行数，表示已经探索完成，返回结果
        if (x >= n) {
            ans = count;
            return;
        }

        // 当列下标 >= 列数，标识当前行探索完成，继续下一行的谈搜
        if (y >= m) {
            dfs(x + 1, 0, rect, count);
            return;
        }

        // 当前所处格已经被填充，则进行下一个格的探索
        if (rect[x][y]) {
            dfs(x, y + 1, rect, count);
            return;
        }

        // k代表每次可以填充的最大长度，取决于当前余下的长宽的最小值，
        // 满足 
        //  - k >= 1
        //  - 区块未被填充
        for (int k = Math.min(n - x, m - y); k >= 1 && isAvailable(rect, x, y, k); k--) {
            // 填充表示覆盖了
            fillUp(rect, x, y, k, true);
            // 跳过k继续探索
            dfs(x, y + k, rect, count + 1);
            // 复原，为了多轮探索的下一轮探索
            fillUp(rect, x, y, k, false);
        }

    }

    public boolean isAvailable(boolean[][] rect, int x, int y, int k) {
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++) {
                if (rect[x + i][y + j]) {
                    return false;
                }
            }
        }
        return true;
    }

    public void fillUp(boolean[][] rect, int x, int y, int k, boolean val) {
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++) {
                rect[x + i][y + j] = val;
            }
        }
    }


}
